package designpatterns.strategy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;


public class InsertionSort extends GeneralSort {
	@Override
	public ArrayList<Integer> sort(ArrayList<Integer> data) {
		internalData = data.toArray(new Integer[data.size()]);
		LinkedList <Integer> list  = new LinkedList <Integer>();
				
		ExecTime = System.currentTimeMillis();
		
		list.add(internalData[0]);
		
		for (int i = 1; i < internalData.length; i++) {
			ListIterator<Integer> iterator = list.listIterator();
			boolean insertBefore = false;
			
			while (iterator.hasNext()) {
				if (internalData[i] < iterator.next()) {
					insertBefore = true;
					break;
				}
			}
			
			if (insertBefore) {
				iterator.previous();
				iterator.add(internalData[i]);
			} else {
				iterator.add(internalData[i]);
			}
		}
				
		ExecTime = System.currentTimeMillis() - ExecTime;
		
		internalData = list.toArray(new Integer[list.size()]);
		
		return new ArrayList <Integer> (list);
	}

	@Override
    public String getName() {
	    // TODO Auto-generated method stub
	    return "InsertionSort " + isSorted();
    }

}
